package getPermutation;


import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        System.out.println(getPermutation(4,9));
    }
    public static String getPermutation(int n, int k) {
        ArrayList<Integer>list=new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        StringBuilder sb=new StringBuilder();
        while(!list.isEmpty()){
            int d=fun(n-1);
            System.out.println((k)/d);
            int index=(k-1)/d;  //要找的元素的索引值
            int value=list.get(index);
            char c=(char) (value+'0');
            sb.append(c);
            list.remove(index);
            n--;
            k=k-(index)*d;
            System.out.println(list.toString());
        }
        return sb.toString();
    }
    //求阶乘
    private static int fun(int n){
        int res=1;
        while(n>1){
            res*=n;
            n--;
        }
        return res;
    }


    // 每一段的长度d是(n-1)!  如果要求第k个，开头的元素的索引值就是(k-1)/d 出去开头 在剩下的集合当中继续寻找，因为是有序的，把剩下的元素看成1->n-1的集合，重复上述操作后找到对应的式子
    // 然后又从第一个元素看其是第几大的元素，原始式子中的就是剩下的元素的第几大的元素      1  3 4   123   k=k-d  d=fun(n-1) 看是再第几段
    // 1234   1   1  1
    // 1243   2   2  2
    // 1324   3   3  1                   1 3 4
    // 1342   4   4  2
    // 1423   5   5  1
    // 1432   6   6  2
    // 2134   7  1  1
    // 2143   8  2  2
    // 2314   9  3  1
    // 2342   10 4  2
    // 2423   11 5  1
    // 2432   12 6  2
    // 3124   13 1  1
    // 3142   14 2  2
    // 3214   15 3  1
    // 3241   16 4  2
    // 3412   17 5  1
    // 3421   18 6  2

    // 123  1
    // 132  2
    // 213  3
    // 231  4
    // 312  5
    // 321  6

}
